# 从 1 开始的斐波那契数列
def climbStairs(n):
    dp = {0: 1, 1: 1}
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


print(2, climbStairs(2))  # 2 2
print(3, climbStairs(3))  # 3 3
